package memory;


import java.util.Arrays;

public class Exercises3 {
    // 300、最长递增子序列
    public int lengthOfLIS2(int[] nums) {
        // 动态规划
        int ret = 0;
        int n = nums.length;
        int[] dp = new int[n];
        // 初始化
        Arrays.fill(dp,1);

        // 填表顺序：从右到左，因为是找后面有多少个子序列
        for(int i = n - 1;i >= 0;i--) {
            for(int j = i + 1;j < n ;j++) {
                if(nums[j] > nums[i]) {
                    // 后面位置的值大于前面位置的值
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }

        return ret;
    }

    public int lengthOfLIS(int[] nums) {
        // 记忆化搜索
        int ret = 0;
        int n = nums.length;
        int[] memo = new int[n];
        for(int i = 0;i < n;i++) {
            // 依每一个数据进行开头，求以其开头的子序列，之后进行比较得到最长的子序列
            ret = Math.max(ret,dfs(i,nums,memo));
        }

        return ret;
    }

    public int dfs(int pos,int[] nums,int[] memo){
        if(memo[pos] != 0) {
            return memo[pos];
        }

        int ret = 1; // 这里需要赋值为1，因为可能pos为之后的值进入不到循环中，但是本身也是一个长度，所以在这里需要进行赋值
        for(int i = pos + 1;i < nums.length;i++) {
            if (nums[i] > nums[pos]) {
                // 说明后面这个值大于上一个pos位置的值，就可以进行计数，之后根究这个i继续王后面进行寻找
                ret = Math.max(ret,dfs(i,nums,memo) + 1); // 这里 +1 是为了把本身的pos位置加上，因为i是从pos+1开始的
            }
        }
        memo[pos] = ret; // 计算pos位置的 子序列长度之后，进行存入到备忘录中，进行优化
        return ret;
    }
}
